package brinaryTree;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * <p>
 * 给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
public class N105_BuildTreeFromInorderAndPreorderTraversal {
    private int[] preorder;
    private int idx_pre;
    private Map<Integer, Integer> val_idx = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.idx_pre = 0;
        for (int i = 0; i < inorder.length; i++) {
            val_idx.put(inorder[i], i);
        }
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int left_index, int right_index) {
        if (left_index > right_index) return null;

        int node_val = preorder[idx_pre];
        TreeNode node = new TreeNode(node_val);

        int index = val_idx.get(node_val);

        idx_pre++;

        node.left = build(left_index, index - 1);
        node.right = build(index + 1, right_index);

        return node;
    }


}
